package zuo.baseUP7_ForceRec;

/**
 * @Author: Forx
 * @Data: 2021/6/19
 * @Desc: Algorithm - zuo.baseUP7_ForceRec
 * @Version: v1.0
 */

/**
 * 我们先写出来一个尝试方法的递归版本,然后针对这个递归结构进行优化
 * 优化的时候已经和原问题无关,只是优化递归的结构
 *
 * try ---> 记忆化搜索 ---->严格表结构 (记忆搜索在某些题目上和严格表结构有同样的时间复杂度)
 *
 * */

import java.util.Arrays;

/**
 *
 * N     : 1 2 3 4 ... N
 * Start : N 中的某一个数
 * End   : N 中的某一个数
 * Key   : 机器人必须走步数
 *
 * 那么S->E,必须是key步,有几种方法
 * */
public class DPDPDP {
    public static int wlkWays(int N,int S,int E,int K){
        return wlkWaysP(N,S,E,K);
    }
    /**
     * 经典递归解法
     *  多了许多不必要的计算 课本上的那个树
     *  这个时候我们可以建立一个数组,来减少
     *  多余的运算
     *  时间复杂度是O(2^K)高度为K的满二叉树的节点数
     *
     *
     * */
    private static int wlkWaysP(int N,int cur,int E,int res){
        if(res==0){
            return cur==E?1:0;
        }
        if(cur==1){
            return wlkWaysP(N,cur+1,E,res-1);//在1的时候只能向右走
        }
        if(cur==N){
            return wlkWaysP(N,cur-1,E,res-1);//在1的时候只能向左走
        }
        return wlkWaysP(N,cur+1,E,res-1) +wlkWaysP(N,cur-1,E,res-1);
    }
    /**
     *
     * 优化版本 --- 记忆化搜索版本
     * 他的时间复杂度可以这样想 只要我填完缓存那就是O(1)
     * 所以我的时间复杂度就在填缓存,缓存只有K*N个,所以
     * 时间复杂度只有O(K*N)
     * */
    public static int wlkWays2(int N,int S,int E,int K){
        int[][]dp = new int[K+1][N+1];//
        for(int[] row : dp){
            for(int e : row){
                e = -1;
            }
        }
        return wlkWaysP2(N,S,E,K,dp);
    }
    private static int wlkWaysP2(int N,int cur,int E,int res,int[][] dp){
        if(dp[res][cur] != -1){
            return dp[res][cur];
        }
        if(res==0){
            dp[0][cur] = cur==E?1:0;
            return dp[0][cur];
        }
        if(cur==1){
            dp[res][cur] = wlkWaysP(N,cur+1,E,res-1);//在1的时候只能向右走
        }else if(cur==N){
            dp[res][cur] = wlkWaysP(N,cur-1,E,res-1);//在1的时候只能向左走
        }else {
            dp[res][cur] = wlkWaysP(N,cur+1,E,res-1) +wlkWaysP(N,cur-1,E,res-1);
        }
        return dp[res][cur];
    }

    /**
     * 严格表结构的优化 --- 这个主要是依赖表中元素的关系如
     * N=5,S=2,K=4,E=4;则dp表如下
     * |index| 0 |  1 | 2  | 3  | 4  | 5  |   ---> dp中的cur 因为N是从1开始的所以col0列废掉了
     * |  0  | * | 0  | 0  | 0  | 1  | 0  |
     * |  1  | * | 0  | 0  | 1  | 0  | 1  |
     * |  2  | * | 0  | 1  | 0  | 2  | 0  |
     * |  3  | * | 1  | 0  | 3  | 0  | 2  |
     * |  4  | * | 0  | 4  |    |    |    |
     *   ^
     *   |
     * 这个是第几步
     *
     *       if(res==0){
     *             dp[0][cur] = cur==E?1:0;
     *             return dp[0][cur];
     *         }
     * 通过这段代码我们可以得知dp的第0行的值只有col4才为1其余的地方为0
     *
     *  if(cur==1)
     *  dp[res][cur] = wlkWaysP(N,cur+1,E,res-1);//在1的时候只能向右走
     *
     *  通过这段代码我们可以得知dp的第col1列的值只依赖于右上角的dp值
     *
     *  if(cur==N) :
     *  dp[res][cur] = wlkWaysP(N,cur-1,E,res-1);//在1的时候只能向左走
     *
     *  通过这段代码我们可以得知dp的第colN列的值只依赖于左上角的dp值
     *
     *  else :
     * dp[res][cur] = wlkWaysP(N,cur+1,E,res-1) +wlkWaysP(N,cur-1,E,res-1);
     *
     * 通过这段代码我们可以得知dp中其他列的值只依赖于右上角的dp值+左上角的dp值
     *
     * 通过这个规律可以完成整个表
     *
     *
     * */
    /**
     *
     * 给定一个硬币数组,和金额,输出最少能达到金额的硬币个数
     * 如[2 7 3 5 3] 金额:10 最少是2由7+3组成
     *
     * */
    /**
     * 返回的是组成金额的最小硬币数
     * */
    private static int getMinKinds(int[] coins,int sum,int curIndex){
        if(sum <0)return -1;
        if(sum == 0){
            return  0;
        }
        if(curIndex == coins.length){
            return -1;
        }
        int got = getMinKinds(coins,sum-coins[curIndex],curIndex+1)+1;
        int dump = getMinKinds(coins,sum,curIndex+1);
        if(got==-1 && dump==-1){
            return -1;
        }
        if(got==-1){
            return dump;
        }
        if(dump==-1){
            return got+1;
        }
        return Math.min( got,dump);
    }
    /**
     * 返回的是组成方法的个数
     * */
    private static int getMinKindsVal(int[] arr,int index,int pre,int aim){
        if(index==arr.length){
            return pre==aim?1:0;
        }
        return getMinKindsVal(arr,index+1,pre,aim) + getMinKindsVal(arr,index+1,pre+arr[index],aim);
    }
    /**
     * 优化版本
     * 变化的时候sum和index
     * 故还是二维表
     * */
    public static int getMinKinds2(int[] coins,int sum){
        int[][]dp = new int[coins.length+1][sum+1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],-2);
        }
        int ans = getMinKinds2P(coins,sum,0,dp);
        for (int i = 0; i < dp.length - 1; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return ans;
    }
    private static int getMinKinds2P(int[] coins,int sum,int curIndex,int[][] dp){
        if(sum <0)return -1;
        if(dp[curIndex][sum]!=-2){
            return dp[curIndex][sum];
        }
        if(sum == 0){
            dp[curIndex][sum] = 0;
            return  0;
        }
        if(curIndex == coins.length){
            dp[curIndex][sum] = -1;
            return -1;
        }
        int got = getMinKinds2P(coins,sum-coins[curIndex],curIndex+1,dp);//产生依赖条件,还有优化空间
        int dump = getMinKinds2P(coins,sum,curIndex+1,dp);
        if(got==-1 && dump==-1){
            return -1;
        }else {
            if(got==-1) {
                dp[curIndex][sum] = dump;

            }else if(dump==-1 ){
                dp[curIndex][sum] = got+1;
            }else {
                dp[curIndex][sum] = Math.min(got+1,dump);
            }
        }

        return dp[curIndex][sum];
    }
    public static int[][] makeDP(int[][] dp,int[] coins,int sum){
        int rows = dp.length;
        int cols = dp[0].length;
        for (int i = 0; i < rows ; i++) {
            /*
            *  if(sum == 0){
            *     dp[curIndex][sum] = 0;
            *     return  0;
            *   }
            *
            * */
            dp[i][0] = 0; //
        }
        for (int i = 1; i < cols ; i++) {
            /*
            * if(curIndex == coins.length){
            *       dp[curIndex][sum] = -1;
            *       return -1;
            *  }
            *
            * */

            dp[rows-1][i] = -1;
        }

        /*
        *int got = getMinKinds2P(coins,sum-coins[curIndex],curIndex+1,dp)+1;//依赖的是下面的元素
        *int dump = getMinKinds2P(coins,sum,curIndex+1,dp);
        *if(got==-1 && dump==-1){
        *   return -1;
        *}else {
        *   if(got==-1 && dump!=-1){
        *        dp[curIndex][sum] = dump;
        *
        *   }else if(dump==-1 && got!=-1){
        *       dp[curIndex][sum] = got+1;
        *   }else {
        *       dp[curIndex][sum] = Math.min(got,dump);
        *   }
        * }
        *
        * */
        for (int curIndex = rows-2; curIndex >=0 ; curIndex--) {
            for (int j = 1; j < cols; j++) {
                int dump = dp[curIndex+1][j]; //int dump = getMinKinds2P(coins,sum,curIndex+1,dp);
                int got = -1;                   //int got = getMinKinds2P(coins,sum-coins[curIndex],curIndex+1,dp)+1;
                if(j-coins[curIndex] >=0){
                    got = dp[curIndex+1][j-coins[curIndex]];
                }
                if(got==-1 && dump==-1){
                    dp[curIndex][j] = -1;
                }else if (got==-1){
                    dp[curIndex][j] =dump;
                }else if(dump==-1){
                    dp[curIndex][j] =got+1;
                }else {
                    dp[curIndex][j] =Math.min(dump,got+1);

                }

            }
        }
        for (int i = 0; i < dp.length - 1; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp;
    }

    public static int getMinKinds3(int[] coins,int sum){
        int[][]dp = new int[coins.length+1][sum+1];
        dp = makeDP(dp,coins,sum);
//        for(int[] row : dp){
//            for(int e : row){
//                e = -2;     //-2表示没算过
//            }
//        }
        return dp[0][sum];//getMinKinds2P(coins,sum,0,dp);
    }
    public static int[][] makeDP2(int[] arr,int sum){
        int N = arr.length;
        int[][] dp = new int[N+1][sum+1];
        for (int i = 0; i <=N; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <=sum ; i++) {
            dp[N][i] = -1;
        }

//        for (int index = N-1; index >=0; index--) {
//            for (int rest = 1; rest <=sum ; rest++) {
//                int p1 = dp[index+1][rest];
//                int p2 = -1;
//                if(sum - arr[index] >=0){
//                    p2 = dp[index+1][sum - ]
//                }
//            }
//        }


        return null;
    }




    public static void main(String[] args) {
        int[] buff = {1,2,3,4,5,6,7,8};
        System.out.println(getMinKinds2(buff,6));
        System.out.println(getMinKinds3(buff,6));
        //System.out.println(getMinKindsVal(buff,0,0,6));
    }



}
